package dnbW.utilW;

import java.util.ArrayList;
import java.util.Iterator;
import java.util.LinkedList;
import java.util.List;
import java.util.TreeMap;

/**
 * This is a class to solve the subset sum problem in mathematics. The algorithm used in this class
 * is the Algorithm 4b introduced in the paper "Computing Partitions with Applications to the Knapsack
 * Problem" by Ellis Horowitz and Sartaj Sahni in ACM'1974.
 * Note: This class is designed to be highly mathematical and tuned for performance. Hence,
 * software design is somewhat less concerned.
 * @author truongbaquan
 */
public class SubsetSumSolver {
    public static void main(String[] args) {
        long[] input = new long[] {1, 1, 2, 3, 3, 4};
        long target = 6;
        try {
            Stopwatch stopwatch = new Stopwatch();
            stopwatch.start();
            SubsetSumSolver solver = new SubsetSumSolver();
            List<Long> results = solver.solve(input, target);
            for (long result : results) {
                long c = result;
                String bitString = Long.toBinaryString(result);
                while (bitString.length() < input.length) {
                    bitString = "0" + bitString;
                }
                System.out.print(bitString + " : ");
                for (int i = 0; i < input.length; i++) {
                    if (c % 2 == 1) System.out.print(input[i] + "  ");
                    c /= 2;
                }
                System.out.println();
            }
            stopwatch.stop();
            System.out.println("Execution Time = " + stopwatch.readTime() + "ms");
        }
        catch (Exception ex) {
            System.err.println(ex.getMessage());
        }
    }

    /**
     * Finds all combinations of input numbers whose sum is equal to target using Algorithm 4b.
     * The combinations are encoded as a binary string (1 if the input number at this place is selected)
     * @param input    The input is assumed to be sorted in ascending order
     * @param target    The target number
     * @return          The list of encoded input combinations
     */
    public List<Long> solve(long[] input, long target) {
        if (input.length > 64) {
            //throw new TooManyInputsException("There are more than 64 inputs which could not be encoded by bitstring.");
            return null;
        }

        List<Long> result = new ArrayList<Long>();
        // Split input[] into two equal arrays input1[] and input2[].
        // Since input[] is sorted, both input1[] and input2[] are sorted.
        long[] input1 = new long[input.length / 2];
        long[] input2 = new long[input.length - input.length / 2];
        for (int i = 0; i < input.length / 2; i++) {
            input1[i] = input[i];
        }
        for (int i = input.length / 2; i < input.length; i++) {
            input2[i - input.length / 2] = input[i];
        }

        TreeMap<Long, List<Long>> possibleSum1 = createPossibleSum(input1);
        TreeMap<Long, List<Long>> possibleSum2 = createPossibleSum(input2);

        Iterator<Long> iter1 = possibleSum1.keySet().iterator();
        Iterator<Long> iter2 = possibleSum2.descendingKeySet().iterator();
        long value1 = iter1.hasNext()?iter1.next():-1;
        long value2 = iter2.hasNext()?iter2.next():-1;
        while (value1 != -1 && value2 != -1) {
            if (value1 + value2 < target)
                value1 = iter1.hasNext()?iter1.next():-1;
            else if (value1 + value2 > target) {
                value2 = iter2.hasNext()?iter2.next():-1;
            }
            else {
                List<Long> bitStringList1 = possibleSum1.get(value1);
                List<Long> bitStringList2 = possibleSum2.get(value2);
                for (long bitString2 : bitStringList2) {
                    for (long bitString1 : bitStringList1) {
                        long resultBitString = bitString2<<input1.length | bitString1; // cascade the two bitstrings
                        result.add(resultBitString);
                    }
                }
                value1 = iter1.hasNext()?iter1.next():-1;
            }
        }
        return result;
    }

    /**
     * Creates an array of all possible sum of the number given in the input array (using Algorithm 2a)
     * @param input The input array (sorted)
     * @return      An array of all possible sum. The length of this array is 2*2^(input.length).
     * For each sum, the next element is the bitstring showing which numbers produce that sum.
     */
    private TreeMap<Long, List<Long>> createPossibleSum(long[] input) {
        TreeMap<Long, List<Long>> result = new TreeMap<Long, List<Long>>();
        long[] array = new long[2*powerOf2(input.length)];

        // first element is (0, 0)
        array[0] = 0;
        array[1] = 0;
        List<Long> firstList = new LinkedList<Long>();
        firstList.add(new Long(0));
        result.put(new Long(0), firstList);

        int ic = 1; // increment counter

        for (int i = 0; i < input.length; i++) {
            for (int j = ic; j < 2*ic; j++) {
                array[2*j] = array[2*j - 2*ic] + input[i];
                array[2*j+1] = array[2*j-2*ic+1] | ic; // bit-wise OR
                List<Long> list;
                if (result.containsKey(array[2*j])) {
                    list = result.get(array[2*j]);
                }
                else {
                    list = new LinkedList<Long>();
                    result.put(new Long(array[2*j]), list);
                }
                list.add(array[2*j+1]);
            }
            ic *= 2;
        }
        return result;
    }

    private static int powerOf2(int exponent) {
        if (exponent < 0) return 0;
        int result = 1;

        for (int i = 1; i <= exponent; i++) {
            result *= 2;
        }
        return result;
    }

    /**
     * This is the class that encapsulates a sum and the bitstrings encoding the numbers whose sum is
     * equal to it.
     */
    private class Sum {
        private long value;

        private long[] array;

        private LinkedList<Long> bitStrings = new LinkedList<Long>();

        public void addBitString(long bitString) {
            this.bitStrings.add(bitString);
        }

        public Sum(long value, long[] array) {
            this.value = value;
            this.array = array;
        }

        @Override
        public boolean equals(Object obj) {
            if (obj == null) {
                return false;
            }
            if (getClass() != obj.getClass()) {
                return false;
            }
            final Sum other = (Sum) obj;
            if (this.value != other.value) {
                return false;
            }
            return true;
        }

        @Override
        public int hashCode() {
            int hash = 5;
            hash = 29 * hash + (int) (this.value ^ (this.value >>> 32));
            return hash;
        }
    }

    /**
     * This exception is thrown when the input array is too long.
     */
    public static class TooManyInputsException extends Exception {
        public TooManyInputsException() {
            super();
        }

        public TooManyInputsException(String message) {
            super(message);
        }
    }
}
